%-------------------------------
%原根习题
%-------------------------------
		\begin{Exercise}
			34对模37的次数是多少？
		\end{Exercise}
		\jd{
			解法一：可以按照定义去求，遍历一个完全系：
			$34^ 0 = 1
			34^ 1 = 34,
			34^ 2 = 9,
			34^ 3 = 10,
			34^ 4 = 7,
			34^ 5 = 16,
			34^ 6 = 26,
			34^ 7 = 33,
			34^ 8 = 12,
			\underline{34^ 9 = 1},
			34^ {10} = 34,
			34^ {11} = 9,
			34^ {12} = 10,
			34^ {13} = 7,
			34^ {14} = 16,
			34^ {15} = 26,
			34^ {16} = 33,
			34^ {17} = 12,
			\underline{34^ {18} = 1},
			34^ {19} = 34,
			34^ {20} = 9,
			34^ {21} = 10,
			34^ {22} = 7,
			34^ {23} = 16,
			34^ {24} = 26,
			34^ {25} = 33,
			34^ {26} = 12,
			\underline{34^ {27} = 1},
			34^ {28} = 34,
			34^ {29} = 9,
			34^ {30} = 10,
			34^ {31} = 7,
			34^ {32} = 16,
			34^ {33} = 26,
			34^ {34} = 33,
			34^ {35} = 12,
			34^ {36} = 1$\par
			由计算结果可知34对模37的次数为9.
			%		for i in range(37):
			%		   print "34^",i,"=",mod(34^i,37)
			
			解法二：\par
			%		sage: euler_phi(37)
			%		36
			%		sage: 36.divisors()
			%		[1, 2, 3, 4, 6, 9, 12, 18, 36]
			%		sage:
			可以证明，$ord_m(a) \mid \varphi(m)$，所以，37的欧拉函数是36，6的所有因子是1, 2, 3, 4, 6, 9, 12, 18, 36，依次计算$a^l (mod\ 37),l \in {1, 2, 3, 4, 6, 9, 12, 18, 36}$,结果为1的l最小取值为次数。
		}
		
		\begin{Exercise}
			判断47，55，59的原根是否存在。若存在，求出其所有原根。
		\end{Exercise}
		\jd{
			47是奇素数，根据定理，我们知道47的原根存在。\par
			55的标准分解式$5 \times 11$，根据定理其不是$2,4,p^l,2p^l$的形式，故55没有原根。\par
			59是奇素数，根据定理，我们知道59的原根存在。\par
		}
		
		\begin{Exercise}
			求47所有原根。
		\end{Exercise}
		\jd{
			47是奇素数，根据定理，我们知道47的原根存在。\par
			$\varphi(47)=46$,46的标准分解式为$2 \times 23$,46互素的因子g为3，5，7，9，$\ldots$，计算$g^{23},g^2$：\par
			$3^{23} \equiv 1,3 ^2\equiv 9$,3不是原根\par
			$4 ^{23}\equiv 1,4 ^2\equiv 16$,4不是原根\par
			$5 ^{23}\equiv 46,5 ^2\equiv 25$,5是原根\par
			$5^l$，l遍历46的缩系，\{ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45 \}，得到所有原根为\{ 5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45 \}.
			
			%#caculate reduced residue system
			%reducedrs=[]
			%for i in range(1,46):
			%if gcd(46,i)==1:
			%reducedrs.append(i)
			%print reducedrs
			%#caculate all primitive roots
			%priroot=[]
			%for i in reducedrs:
			%priroot.append(mod(5^i,47))
			%priroot.sort()
			%print priroot
			%#verify all primitive root
			%for i in priroot:
			%print "the euler function of 47 is 46,the order of ",i," module 47 is ",Mod(5,47).multiplicative_order(),"."		
		}
